#include<iostream>
#include<algorithm>
#include<vector>
#include<iostream>
const int maxn=256;
using namespace std;
//best-fit
struct part1{
    bool operator<(const part1& other) const
    {
	return begin<other.begin;
    }
    bool operator==(const part1& other) const{
	return name==other.name;
    }
    friend ostream& operator<<(ostream& os,const part1& A)
    {
	return os<<"\t"<<A.name<<"\t"<<A.begin<<"\t"<<A.size<<"\t"<<A.status;
    }
    string  name;       //分区名字
    int     begin;      //起始地址
    int     size;       //分区大小
    int     status;	//state
};
struct part2{
    bool operator==(const part2& other) const{
   	 return begin==other.begin;	
    } 
    bool operator<(const part2& other) const{
	return size<other.size;
    }
    friend ostream& operator<<(ostream& os,const part2& A){
	return os<<"\t"<<A.begin<<"\t"<<A.size<<"\t"<<A.status;
    }
    int     begin;
    int     size;
    int     status;
};
bool cmp(part2 A,part2 B) {
     return A.begin<B.begin;
}
vector<part1>M;
vector<part2>free_table;
vector<part2>busy_table;


int find_free_zone(const int& size)
{
     int result=-1;
     vector<part2>::iterator it;
     for(it=free_table.begin();it!=free_table.end();it++)
     {
	 if(it->size>=size)
	 {
	     result=it->begin;
	     it->size-=size;
	     it->begin+=size;
	     if(it->size==0){
		free_table.erase(it);
	     }
	     break;
	 }	     
     }
     sort(free_table.begin(),free_table.end());
     return result;
}
void addhomework(const string& _name,const int& _size)
{
     int result=find_free_zone(_size);
     if(result==-1)
     {	
	cout<<"error: no extra free memory!"<<endl;
	return ;
     }  
     for(int i=0;i<M.size();i++)
     {
	if(result>=M[i].begin&&result<=M[i].begin+M[i].size&&M[i].status==0)
	{
		if(_size==M[i].size)
		{
		   M[i].name=_name;	   
		   M[i].status=1;
		}
		else{
		   M[i].begin+=_size;
		   M[i].size-=_size;
		   M.push_back({_name,result,_size,1});
		}
		break;
	}
     } 
     sort(M.begin(),M.end());
     busy_table.push_back(part2{result,_size,1});
     sort(busy_table.begin(),busy_table.end());
}
template<class T>
void unio(vector<T>& v)
{
     for(int i=0;i<(int)v.size()-1;i++)
     {
	 if(v[i].begin+v[i].size==v[i+1].begin&&v[i].status==0&&v[i+1].status==0)
	 {
		v[i].size+=v[i+1].size;
	        v.erase(v.begin()+i+1);	
		i--;
		break;
	 }
     }
}

void deletehomework(const string& name){
     auto it = find(M.begin(),M.end(),part1{name,0,0,0});
     if(it==M.end())
     {
	     cout<<"can not find the homework"<<endl;
	     return;
     }
     int start = it->begin;     
     it->status=0;it->name="空闲区";          
     auto it2= find(free_table.begin(),free_table.end(),part2{start,0,1});
     it->status=0;
     free_table.push_back(part2{start,it->size,0});
     sort(free_table.begin(),free_table.end(),cmp); 
     unio(M);
     unio(free_table);
     sort(free_table.begin(),free_table.end());

     auto it3=find(busy_table.begin(),busy_table.end(),part2{start,0,1});
     busy_table.erase(it3);
     sort(busy_table.begin(),busy_table.end());
}
void output()
{
     printf("\n内存使用情况\n");
     printf("\t分区名\t起始地址\t分区大小\t状态\n");
     for(auto& i:M) cout<<i<<endl;
     printf("\n空闲分区表：\n");
     printf("\t起始地址\t分区大小\t状态\n");
     for(auto& i:free_table) cout<<i<<endl;
     printf("\n已分配分区表：\n");
     printf("\t起始地址\t分区大小\t状态\n");
     for(auto& i:busy_table) cout<<i<<endl;
}
void init(){
     free_table.push_back(part2{0,maxn,0});
     M.push_back(part1{"空闲区",0,maxn,0});
     addhomework("OS",10);
}
void solve(){
     addhomework("作业1",10);
     addhomework("作业4",25);
     addhomework("作业3",20);
     addhomework("作业2",45);
     deletehomework("作业3");
     deletehomework("作业4");
     deletehomework("作业1");
}
int main(void){

     init();
     solve();
     output();
}
